// https://www.lintcode.com/problem/paint-fence/

public class Solution {
    /**
     * @param n: non-negative integer, n posts
     * @param k: non-negative integer, k colors
     * @return: an integer, the total number of ways
     */
    public int numWays(int n, int k) {
        // write your code here
        // 不存在超过2个相邻的柱子颜色相同，意思就是最多两个相邻的柱子颜色相同。
        // 第1个柱子有k种方案，第2个柱子有k^2种，构造初始条件。
        // 对于第i个柱子，取法是以下两个场景的和：与第i - 1个不一样，已第i - 2个不一样。
        if ((n == 0) || (k == 0)) {
            return 0;
        }
        int[] plans = new int[]{k, k * k};
        if (n == 1) {
            return plans[0];
        } else {
            int i = 2;
            while (i < n) {
                int tmp = plans[1] * (k - 1) + plans[0] * (k - 1);
                plans[0] = plans[1];
                plans[1] = tmp;
                ++i;
            }
            return plans[1];
        }
    }
}